Multicasting data is an important and efficient communications technique that is widely used in many communications environments. Multicasting permits numerous (n) network elements or communicatively coupled stations to receive a data unit without requiring establishment of n separate connections between a sender and the n stations. As is well understood by those skilled in the art, powerline networks are one example of a communications environment in which multicasting is used.
FIG. 1 schematically illustrates a typical powerline network including a part of a power distribution network 8 to which a plurality of stations 10 are connected. The stations 10 provide two interfaces: a physical layer interface to the power distribution network 8, and a link layer interface (as will be further explained below with reference to FIG. 2). The link layer interface provides a home networked device 12 with media access control (MAC) layer functionality. As will be appreciated by those skilled in the art, the home networked device 12 may also include network, transport, session, presentation and application layers.
Each station 10 is connected to the power distribution network 8, and uses the power distribution network 8 as a physical layer shared medium for transporting data. It has been established that orthogonal frequency division multiplexing (OFDM) is a suitable method for modulating a data signal for transmission over the shared medium, such as the power distribution network 8.
FIG. 2 schematically illustrates principal functional blocks of the station 10 shown in FIG. 1. The station 10 includes a powerline modulator and demodulator 16 (modem) that provides the physical layer interface, a device input/output 18 (I/O) that enables the link layer interface, a frame and medium access control service 20, and a link management service 22.
The powerline modem 16 typically uses OFDM and a concatenated forward error correction scheme during the transmission of data. The device I/O 18 provides MAC level primitives to the home networked device 12, and is therefore adapted to exchange data transported by the physical layer with the home networked device 12.
The frame and medium access control service 20 receives data from the home networked device 12 through the device I/O 18. If the data does not fit in a single MAC protocol data unit (MPDU), the data is segmented and reassembled by the frame and medium access control service 20. The data is framed in one or more MPDU payloads in accordance with a suitable MAC layer protocol, and is transported by the physical layer, accordingly. In order for the station 10 to transmit a frame, the station 10 must first acquire access to the medium. In accordance with the powerline networking implementations, access to the medium is enabled by monitoring a state of the medium using a carrier sense to determine when access may be requested in accordance with a predefined, distributed procedure. Stations contend for the access using an exponential back-off algorithm, when permitted to contend by rules of the predefined distributed procedure. The frame and medium access control service 20 also performs delivery control to ensure that each message for which a response is expected, is acknowledged, and that retry procedures are effected when required.
Well known delivery control techniques provide more reliable multicast message delivery. In order for multicast messages to be reliably delivered, acknowledgements (ACKs) need to be returned to a sender from receivers. If multiple stations respond to a multicast message, collision occurs. It is therefore known in powerline networking environments, to select a station as a proxy for all of the receivers of the multicast message so that only one response is received at the transmitting station.
Link management service 22 performs physical (PHY) and MAC management functions, exchanges necessary messaging with the other stations, and evaluates link level operations in a known manner. For example, the link management service 22 formulates and issues, under predefined conditions, physical layer feedback relating to a condition of the medium as it pertains to a quality of signaling between the station 10 and the other stations communicatively coupled to the network. The physical layer feedback in an OFDM modulation scheme is typically a tone map. The tone map indicates which of a plurality of orthogonal frequency channels (tones) defined by the OFDM standard, are currently to be used for communicating with an identified one of the other stations. On average, a tone map is likely to become obsolete in a matter of seconds. Consequently, the tone maps are typically renewed in accordance with a predefined algorithm. A more detailed description of tone map renewal is provided in Applicant's co-pending U.S. patent application Ser. No. 09/932,945, filed on Aug. 21, 2001 entitled METHOD AND APPARATUS FOR CONSTRUCTING A SUB-CARRIER MAP, which is incorporated herein by reference.
FIG. 3 schematically illustrates a multicast transmission format in accordance with a Homeplug® standard. The data is transported in a frame that is bounded by a start of frame delimiter, and an end of frame delimiter. A third delimiter (a response delimiter) is issued by a station selected as a proxy by the sender, after the frame is transmitted. Separating the frame and the end of frame delimiter is an end of frame gap; and separating the end of frame delimiter and the response delimiter, is a response interframe space. The interval required to transmit a multicast frame and receive a response is hereinafter referred to as a transmission interval. Each transmission interval is preceded by a contention resolution period during which the sending station obtains access to the medium, in a manner well known in the art.
The delimiters (start of frame, end of frame and response) all have substantially the same format. They include a preamble 52,56,62, and a frame control section 50,58,60. The preamble is used by physical layer transmission equipment for such purposes as automatic gain control, etc. The content of the frame control 50,58,60 and frame body 54 is passed up to the medium access control (MAC) layer to provide an indication of the data/response. The content of the frame control 50,58,60 includes medium control information 50b,58b,60b, including contention control bits 50a,58a,60a that indicate whether the frame conveys a segment defined in accordance with a segment bursting feature of the Homeplug® protocol. Each delimiter further indicates whether it is a start of frame, end of frame, or response delimiter. The start of frame delimiter indicates a length of the frame.
The frame consists of a frame body 54 having a header portion 54a, followed by a content portion, and ending with a checksum 54c. The frame body 54 consists of a segment control (SC) section, and addressing fields; including a destination address field 54a2. The segment control section contains a multicast flag 54a1. The multicast flag 54a1 is set when the address in the DA field points to the proxy rather than the multicast address. During multicast transmissions these fields are universally inspectable, i.e. any station that detects the start of frame delimiter also inspects these fields to determine if the frame is addressed to the station
The content portion is the only part of this frame that is of variable length (up to a predetermined maximum number of symbols), and is the only part that may be encrypted. Information relating to a length the frame body 54 and an indication of whether a response is expected are specified in the medium control information 50b in the frame control 50, so that, upon receipt of a start of frame delimiter, any station can determine when the current transmission interval ends, and a next contention resolution period begins. The content is not universally inspectable, and is generally longer than the universally inspectable portion of the frame. It contains a payload with pad bits, in any frame, but, given that the frame illustrated is a multicast frame, the multicast flag 54a1 is set, the address in the destination address field 54a2 is the address of a chosen proxy, and the payload is prefixed by a multicast frame extension 54b containing a 6 byte multicast destination address. The multicast frame extension 54b may be a MAC management entry of a multicast with response type. The multicast destination address 54b is the destination address that is to be associated with the data. However, since the MAC layer is designed to ensure that only frames addressed to the receiving station are responded to, the address of the proxy is inserted into the destination address (DA) field 54a2.
FIG. 4 is a flow chart illustrating a prior art procedure for transmitting multicast messages. The procedure begins, in step 100 when a frame and medium access control algorithm 20 receives data from either the device I/O 18, or the link management service 22 (FIG. 2) to be multicast. The multicast frame extension 52 is created for the frame (step 102).
An address of a proxy selected randomly, or as a station least likely to receive the frame is inserted into an address field of the frame (step 104). As explained above, the destination address field 54a2 in a header part of the frame body 54 used for specifying the proxy address when the multicast flag 54a1 is set. If the data does not fit in a single frame payload, it is divided into a plurality of segments, each sized to fit in a payload portion of a frame (step 105).
The data is then framed, and signaling and control bits well known in the art, are inserted into the fields of the frame overhead, the frame delimiters, etc. (step 106A).
The frame and medium access control services 20 then obtain access to the medium (step 107), and transmit the frame (step 108). If the frame carries one of a plurality of segments, it is identified as such using the segment control field (last segment flag), and contention control bits in the start and end of frame delimiters (unless the frame carries the last segment), are used to assert privileged access to the medium in a subsequent transmission interval, using a well known technique called segment bursting. Once the frame is sent, a response timer is set (step 110) by the frame and medium access control algorithm 20. If a response to the multicast message is received (as determined in step 112) before the response timer expires (in step 113), the multicast frame is deemed successfully sent, and the retry count is reset to zero (step 114). If the multicast frame is deemed successfully sent, it is determined in step 115 if another segment exists. If another segment is awaiting delivery, the procedure returns to step 107, and the frame containing the next segment is transmitted (after access to the medium is obtained). Otherwise, the procedure ends successfully.
If the timer expires before a response is received by the frame and medium access control algorithm 20 (as determined in step 113), a collision is inferred (step 116), and a retry procedure is applied. The retry procedure involves incrementing a retry counter (step 118), and determining if the retry count exceeds a predefined number of retries. If the retry count is greater than the predefined number (as determined in step 120), the multicast message has not been acknowledged in spite of repeated retries, and a delivery failure is declared (step 122). Accordingly, the source of the data may be sent a delivery failure notice. Even if only one of a plurality of segments is not deliverable, the entire packet is deemed undelivered. On the other hand, if the retry count is less than the predetermined number (step 120), the procedure backs off (step 124), and returns to step 107. As is well known in the art, back-off entails setting a timer (for an extended interframe space+a random back-off time) and waiting for the timer to expire before sending a frame. If any transmission is sensed in the meantime and a next contention resolution period is determined, the timer is annulled.
The method described above with reference to FIG. 4 is disclosed in U.S. Pat. No. 6,522,650, entitled MULTICAST AND BROADCAST TRANSMISSION WITH PARTIAL ARQ, which issued to Yonge et al. on Feb. 18, 2003. Yonge et al. teach the procedure for selecting a multicast proxy. The multicast proxy is selected from a set of the stations from which transmission feedback is received. Preferably, the selection is narrowed to the members of the multicast group. The selection is either random, or a station is chosen that appears to be least likely to correctly receive and respond to the message.
However, extensive experimentation has shown that implementation of Yonge et al's partial-ARQ (automatic repeat request) can result in network performance degradation. In accordance with Yonge's teachings the same proxy is used each time a multicast frame is sent, unless a random proxy selection is forced for each multicast packet, or a valid channel map has been received that indicates a station having a lower transmission bandwidth than a currently selected multicast proxy when a multicast packet is to be sent. Thus, if the selected proxy becomes unavailable or fails to respond for any reason, delivery failure ensues. Furthermore, if the proxy station becomes disconnected from the network, or enters an energy saving or ‘sleep’ mode, the station may not be able to respond to multicast messages, resulting in unproductive retransmission of the multicast frame, and eventually, a delivery failure.
There therefore remains a need for a method for selecting a proxy for responding to a multicast message that ensures reliable network performance and reduces transmission delivery failures.